/* ************************************************************************
> File Name:     3.c
> Author:        zhfu
> mail:          3346897597@qq.com
> Created Time:  2022年04月18日 星期一 16时43分01秒
> Description:   
 ************************************************************************/
#include<stdio.h>
#define MAX_ROW 5
#define MAX_COL 5

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0
};

/*创建pointer数据结构来标记经过的点*/
struct pointer
{
    int row;
    int col;
};

struct pointer route[25];
int top = 0;

void push(int row, int col)
{
    struct pointer p = {row, col};
    route[top++] = p;
}

struct pointer pop()
{
    return route[--top];
}

void print_routine()
{
    int i = 0;
    printf("(0, 0)->");
    while (!(route[i].row == 4 && route[i].col == 4)){ /*不等价于route[i].row != 4 && route[i].col != 4，中间应该是||*/
        printf("(%d, %d)->", route[i].row, route[i].col);
        ++i;
    }
    printf("(4, 4)\n");
}

void back_tracing(struct pointer p)
{
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1){
        print_routine();
        return;
    }
    
    int key = 1;

    if (p.row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0){
        key = 0;
        push(p.row + 1, p.col);
        maze[p.row + 1][p.col] = 2;
        struct pointer tmp = {p.row + 1, p.col};
        back_tracing(tmp);
        pop();
        maze[p.row + 1][p.col] = 0;
    }

    if (p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0){
        key = 0;
        push(p.row, p.col + 1);
        maze[p.row][p.col + 1] = 2;
        struct pointer tmp = {p.row, p.col + 1};
        back_tracing(tmp);
        pop();
        maze[p.row][p.col + 1] = 0;
    }

    if (p.col - 1 >= 0 && maze[p.row][p.col - 1] == 0){
        key = 0;
        push(p.row, p.col - 1);
        maze[p.row][p.col - 1] = 2;
        struct pointer tmp = {p.row, p.col - 1};
        back_tracing(tmp);
        pop();
        maze[p.row][p.col - 1] = 0;
    }

    if (p.row - 1 >= 0 && maze[p.row - 1][p.col] == 0){
        key = 0;
        push(p.row - 1, p.col);
        maze[p.row - 1][p.col] = 2;
        struct pointer tmp = {p.row - 1, p.col};
        back_tracing(tmp);
        pop();
        maze[p.row - 1][p.col] = 0;
    }

    if (key)
    {
        return;
    }
}

int main()
{
    struct pointer p = {0, 0};
    back_tracing(p);

    return 0;
}
